﻿#include <list>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define First  65   //字符A
#define Last  122   //字符z
int num = 0;   //树结点的编码
int wt[Last + 1] = { 0 };    //空间换时间，记录输入文件中的字符数目

//树结点的结构体
typedef struct Node
{
	char value = Last + 1;  //字符内容
	int weight;  //权重
	int brother;  //兄弟结点
	int parent;  //父结点
	int code = 0;     //每个结点的编码
	string huffCode;  //哈夫曼编码
}Node;

vector<Node> tree;  //存储树的vector
list<Node> sortList;  //用于排序以构造树的list

//定义list的排序方法
bool compareWeight(const Node &n1, const Node &n2)
{
	return n1.weight < n2.weight;
}

//tree由编号排序
bool compareCode(const Node &n1, const Node &n2)
{
	return n1.code < n2.code;
}

//tree由字符value排序
bool compareValue(const Node &n1, const Node &n2)
{
	return n1.value < n2.value;
}

//初始化所有结点
bool initTree(string s)
{
	if (s.empty())
		return false;
	for (int i = 0; i < s.size(); ++i)
		++wt[(int)s[i]];
	//将权值赋给结点
	for (int j = First; j <= Last; ++j)
	{
		if (wt[j] != 0)
		{
			Node n;
			n.weight = wt[j];
			n.value = (char)j;
			sortList.push_back(n);  //结点存入sortList
		}
	}
	return true;
}

//从sortList取出一个结点
Node getNode()
{
	Node n = sortList.front();
	sortList.pop_front();
	return n;
}

//使两个结点进树
void pushTwoNode(Node &n1, Node &n2)
{
	tree.push_back(n1);
	tree.push_back(n2);
}

//给新进树结点记录编码
void markCode(Node &n)
{
	if (n.code == 0)
		n.code = num++;
}

void makeRelation(Node &n1, Node &n2, Node &par)
{
	n1.parent = par.code;
	n2.parent = par.code;
	n1.brother = n2.code;
	n2.brother = n1.code;
}

//从sortList取两个结点
void popTwoNode(Node &n1, Node &n2)
{
	Node n;
	n1 = getNode();
	n2 = getNode();
	//记录孩子结点与父节点的编码
	markCode(n1);
	markCode(n2);
	markCode(n);
	//构造孩子结点与父节点的关系
	makeRelation(n1, n2, n);
	//权重之和的结点再次存入sortList
	n.weight = n1.weight + n2.weight;
	sortList.push_back(n);
}

void handleMin()
{
	Node n1, n2;
	//从sortList取两个权重最小的结点
	popTwoNode(n1, n2);
	//将这两个结点存入树
	pushTwoNode(n1, n2);
}

//构造哈夫曼树
void HuffmanTree()
{
	//剩余一个结点时循环结束
	while (sortList.size() != 1)
	{
		sortList.sort(compareWeight);  //给list排序
		handleMin();   //处理两个权重最小的元素
	}

	tree.push_back(sortList.back());  //存入树的根结点
}

//根据每个结点的code从小到大排序
void vectorCodeSort()
{
	sort(tree.begin(), tree.end(), compareCode);
}

//根据每个结点的value从小到大排序
void vectorValueSort()
{
	sort(tree.begin(), tree.end(), compareValue);
}

//读取哈夫曼编码
void readHuffCode()
{
	for (int i = 0; i < tree.size() - 1; ++i)
	{
		if (isalpha(tree[i].value) != 0)
		{
			string huff;
			int cod = tree[i].code;
			while (cod != tree.size() - 1)
			{
				if (tree[cod].brother > tree[cod].code)
					huff.append("0");
				else
					huff.append("1");
				cod = tree[cod].parent;
			}
			tree[i].huffCode = huff;
		}
	}
}

int main()
{
	string s = "aabbbccc";

	//初始化整个sortListlist
	if (initTree(s))
	{
		//构造哈夫曼树
		HuffmanTree();

		//给vector内的元素排序
		vectorCodeSort();

		//得到哈夫曼编码
		readHuffCode();

		//根据value进行排序，便于输出
		vectorValueSort();
	}

	for (int i = 0; i < tree.size(); ++i)
	{
		if (isalpha(tree[i].value) == 0)
			break;
		cout << tree[i].value << " " << tree[i].huffCode << endl;
	}

	system("pause");
}